Conventionally, the representative authentication methods include a user authentication scheme for checking an authenticity of a system user, a message authentication scheme for proving that a message is an authentic one, and a digital signature scheme in which they are combined further and the information producer guarantees that a produced message is an authentic one. Here, the user authentication scheme, the message authentication scheme, and the digital signature scheme will be briefly explained with references to the respective figures.
FIG. 1A is a conceptual diagram of an authentication scheme according to the Fiat Shamir scheme which is the representative example of the user authentication scheme. (A. Fiat and A. Shamir: "How to prove yourself, practical solutions to identification and signature problems", Proc. of Crypto' 86, 1986.5, and U.S. Pat. No. 4,748,668.
According to this Fiat Shamir scheme, when a party (referred hereafter as a prover) which owns a secret information s tries to prove its authenticity to a verifier, it is authenticated as follows, with N (=pq: p and q are mutually different large prime numbers) and I (=s.sup.2 (mod N)) as the public information of the prover, and s, p and q as the secret information of the prover.
First, at the beginning, the prover generates a random number R, calculates a preresponsive message X=R.sup.2 (mod N), and sends X to the verifier. The verifier who received said X selects 0 or 1 randomly as a check bit e, and sends e to the prover. The prover who received said e calculates a responsive message Y=Rs.sup.e (mod N), and sends Y to the verifier. The prover who received said Y verifies whether a verification formula y.sup.2 =X.times.I.sup.e (mod N) holds.
By setting what are up to this point as one round, and repeating this for t rounds, a probability for a third party who does not know the secret information s to clear the verification formula of the verifier becomes (1/2.sup.t). Therefore, when the authentication is finished normally for sufficiently large t, the verifier may very well judge that the verification target (prover) is an authentic prover who owns the secret information s.
Here, this authentication scheme is generally referred as an authentication scheme based on the zero knowledge interactive proof, which has a merit in that the prover notifies only a fact that it owns the secret information s to the verifier, without leaking other contents related to the secret information s at all.
However, in the Fiat Shamir scheme, there has been a problem that the log for the prover and the verifier cannot be used later on as an evidence for a fact that the verifier has authenticated the prover. For this reason, there is a proposition of an authentication scheme in Sakurai (Japanese Patent Application Laid Open No. 5-12321) as a solution method for this problem. According to this authentication scheme, it is said that, an evidence for a fact that the verifier has really authenticated the prover remains even after the verifier has authenticated the prover.
However, what remains as an evidence here is only for a fact that the verifier authenticated the prover through a communication at best, and apart from this authenticated fact, it does not refer to anything as to what kind of communication has been made, such as the communication content in the first place. Also, because it records and maintains all the communication sequences as the evidence of the authenticated fact, there is also a drawback in that an amount of information that must be recorded and maintained by the verifier is large.
Next, FIG. 1B is a conceptual diagram of an authentication according to an authenticator which is one example of a message authentication. According to this authentication scheme, the prover who wishes to transmit a message M produces an authenticator h.sub.k (M) for the message M by utilizing the hash function h with a secret key K.sub.h as a parameter, and transmits said authenticator along with said message M to the verifier who is a transmission target. The verifier is secretly sharing the same secret key K.sub.h as the prover in advance, so that it produces the authenticator by using the secret key K.sub.h from the received message similarly as in the above, and checks by matching with the received authenticator. When this matching is succeeded, the authenticity of the received message is guaranteed. This is because the correct authenticator for an arbitrary message cannot be produced without knowing the secret key K.sub.h.
However, both of the above described user authentication and message authentication basically have the main object in preventing an illegal act by a third party, and what is guaranteed by a fact that said user authentication has normally finished is a fact that the prover is an authentic owner of the secret information at best, that is only a fact that a third party has not been utilizing it illegally, while what is guaranteed by a fact that a matching check has succeeded in said message authentication is only a fact that an illegal act by a third party such as an alteration of the message has not been made. Therefore, both of the above two authentication schemes are effective only against the illegal act by the third party in principle, and a fact that they have no effectiveness against the illegal act by the prover or the verifier at all is the drawback.
Next, FIG. 1C is a conceptual diagram of an RSA signature scheme (R. L. Rivest, A. Shamir, L. Adleman, "A method for obtaining digital signatures and public-key cryptosystem", Comm. ACM, vol. 21, No. 2, 1978.2) which is one example of the digital signature.
According to the RSA signature scheme, it is authenticated as follows, with e and N (=pq: p and q are mutually different large prime numbers) as the public information of the signer, and d[e.times.d (mod(p-1)(q-1))=1], p and q as the secret information of the signer.
First, the signer calculates a signed message C=M.sup.d (mod N) in order to guarantee that the message M is certainly what is produced by the signer, and transmits C to the verifier. The verifier who received said C calculates M=C.sup.e (mod N), and judges the authenticity of the obtained message M. At this point, when it is judged that the obtained message M is authentic, it is guaranteed that the received message M is definitely what is produced by the signer.
This is because a correct signed message for an arbitrary message cannot be produced without knowing the secret information d, and in addition, the secret information d is unique to each individual and it differs for each individual, so that the signer himself is also going to be specified. Therefore, such illegal acts in which the third party or the verifier alters the message content, or the signer denies the message content are considered to be difficult.
However, this only has an effect since a point at which the exchange of the messages has normally finished at best, and there is no guarantee for what is before that, i.e., guarantee as to whether the transmitted signed message c has surely reached to the verifier from a viewpoint of the signer, so that once it is claimed that the signed message c has not been received by the verifier, there is no means for the signer to oppose that claim, which is a drawback:
In a case in which the information provider provides a message requested by the user, it is necessary to satisfy the following four conditions, namely:
(1) the user authentication for guaranteeing that it is the authentic user;
(2) the delivery proof for guaranteeing that the information provider has surely provided the message requested by the user, and the user has received the provided message;
(3) the content proof that the provided message is the authentic one, which is capable of preventing the illegal act such as the alteration; and
(4) the fact that all of (1) to (3) can be proved later on as the information provider presents evidences such as a log, etc. to an arbitrator according to the need.
However, as explained in the conventional schemes, the Fiat Shamir scheme satisfies (1) alone, the scheme of Sakurai (Japanese Patent Application Laid Open No. 5-12321) satisfies only (1) and a part of (4) (only an evidence for the user authentication), the message authentication satisfies only a part of (3) (only a guarantee that the message is authentic), and the RSA signature scheme satisfies only (3), so that there has been a drawback that the information provider cannot oppose at all against some kind of illegal act, such as an improper claim in which the user says the provided message has not been received despite of the fact that it has been received, as in (2) in particular.